package com.example.lcpractice.heading_offer;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * [剑指 Offer 21]调整数组顺序使奇数位于偶数前面.java
 * <p>
 * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
 * <p>
 * 示例：
 * <p>
 * 输入：nums = [1,2,3,4]
 * 输出：[1,3,2,4]
 * 注：[3,1,2,4] 也是正确的答案之一。
 * 提示：
 * <p>
 * 0 <= nums.length <= 50000
 * 0 <= nums[i] <= 10000
 */
public class q21 {

    public static void main(String[] args) {
        int[] nums = {1, 8, 9, 6, 4, 3, 7, 22};
        System.out.println(Arrays.toString(exchange2(nums)));
    }

    public static int[] exchange(int[] nums) {
        ArrayList<Integer> odd = new ArrayList<>();
        ArrayList<Integer> even = new ArrayList<>();
        for (int num : nums) {
            if (num % 2 == 0) {
                even.add(num);
            } else {
                odd.add(num);
            }
        }
        odd.addAll(even);
        for (int i = 0; i < odd.size(); i++) {
            nums[i] = odd.get(i);
        }
        return nums;

    }

    /**
     * 双指针法：同时移动左右指针，遇到左第一个偶数便和右低一个奇数交换
     * 停止条件是左指针不在右指针的左边
     * @param nums 未排序数组
     * @return 排序数组
     */
    public static int[] exchange2(int[] nums) {
        int i = 0, j = nums.length - 1, tmp;
        while (i < j) {
            while (i < j && (nums[i] & 1) == 1) {
                i++;
            }
            while (i < j && (nums[j] & 1) == 0) {
                j--;
            }
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }
}
